# -*- coding: utf-8 -*-
__author__ =  'Ruben Ribeiro && Rafael Passos'

from random import uniform
from time import clock
from heapsort import HeapSort
from bubblesort import Bubble
from quicksort import QuickSort
from mergesort import MergeSort
from insertionsort import InsertionSort
from random import randint
import matplotlib.pyplot as plt
import pylab as p
import random
import sys
import os
import math

sys.setrecursionlimit(10000)
	
class Main:
	'''Classe principal do programa'''
	listSize = None
	unsortedList = []

	tests = 25
	space = 200
	limit = 1000
	opt = None
	listType = None

	def __init__(self):
		'''Construtor da classe
		Aqui vamos pedir ao utilizador para escolher algumas opções através da consola,
		poderá escolher se quer ver o gráfico com as médias e erro relativo de cada
		algoritmo individualmente ou se querem ver a média de todos no mesmo gráfico,
		poderá ainda escolher se quer testar com lista criadas de ordem aleatória ou 
		ordenadas inversamente.
		'''
		print ("")
		print ("Ver as médias de tempos e as margens de erro relativo de um algoritmo")
		print ("1- HeapSort | 2- BubbleSort | 3- InsertionSort | 4- MergeSort | 5- QuickSort")
		print ("")
		print ("0- Ver a média de tempos de todos os algoritmos num gráfico")
		print ("")
		while True:
			try:
				input = int(raw_input('Escolha uma opção: '))
				if input in range(0,6):
					self.opt = input
					break
				else:
					print 'Escolha uma opção disponível.'
			except:
				print ("Escolha um número")
		print ("")
		print ("1- Lista aleatória | 2- Lista inversa") 
		print ("")
		while True:
			try:
				input = int(raw_input('Escolha o tipo de lista a utilizar: '))
				if input in range(1,3):
					self.listType = input
					break
				else:
					print 'Escolha uma opção disponível.'
			except:
				print ("Escolha um número")
		print ("Opcão seleccionada: %s | Testes em cada algoritmo: %s"%(self.opt, self.tests))
		print ("São testadas %s listas de %s em %s até terem %s elementos"
			%(((self.limit/self.space)), self.space, self.space, self.limit))
		if self.listType == 1:
			print ("Lista Aleatória")
		elif self.listType == 2:
			print ("Lista Inversa")
		print ("")
		self.growingSize(self.tests, self.space, self.limit+1, self.opt, self.listType)

	def generateRandomList(self, size):
		'''Método que gera uma lista com números aleatórios entre 1 e 1000
		@param size -> número de elementos que a lista irá conter
		'''
		self.size = size
		return [randint(1,1000) for r in range(size-1)]

	def generateInverseList(self, size):
		'''Método que gera uma lista com números ordenados inversamente entre 1 e 1000
		@param size -> número de elementos que a lista irá conter
		'''
		self.size = size
		return range(size-1,0,-1)

	def calcAverageVar(self, n, times):
		'''Método que calcula a média e variância com base nos valores recebidos
		@param n -> número de elementos da lista que gerou os tempos
		@param times -> lista com os tempos obtidos
		'''
		self.n = n
		average = reduce(lambda x, y: x + y, times) / len(times)
		var = reduce(lambda x, y: x + (y-average)**2, [0] + times) / len(times)
		return n, average, var

	def expectedCurve(self, values):
		'''Método que calcula as médias mediante uma constante que simula um processador
		e o valor de elementos contidos na lista.
		@param values -> lista de valores para calcular as médias mediante uma constante 
		que simula um processador
		'''
		if (self.opt == 1):
			ct = 61e4
			return [(n * (math.log(n,2)))/ct for n, media, var in values]
		elif (self.opt == 2):
			ct = 18e6
			return [n**2/ct for n, media, var in values]
		elif (self.opt == 3):
			ct = 4e8
			return [n**2/ct for n, media, var in values]
		elif (self.opt == 4):
			ct = 108e4
			return [(n * (math.log(n,2)))/ct for n, media, var in values]
		elif (self.opt == 5):
			ct = 116e3
			return [(n * (math.log(n,2)))/ct for n, media, var in values]
			#ct = 79e5
			#return [n**2/ct for n, media, var in values]

	def growingSize(self, tests, space, limit, opt, listType):
		'''Método que chama o/s algoritmo/s a testar conforme a opção escolhida para gerar 
		os tempos, imprimi-los na consola e chamar a função para criar o gráfico com esses valores
		@param tests -> número de testes a realizar em cada cada lista
		@param space -> valor mínimo e de incrementação de elementos em cada lista nova
		@param limit -> limite de elementos na lista
		@param opt -> opção escolhida
		@param listType -> tipo de lista escolhida
		'''
		self.space = space
		self.limit = limit
		self.tests = tests
		self.listSize = range(space+1, limit + 1, space)
		self.heapSortValues = []
		self.bubbleSortValues = []
		self.insertionSortValues = []
		self.mergeSortValues = []
		self.quickSortValues = []

		for n in self.listSize:
			if listType == 1:
				self.unsortedList = self.generateRandomList(n)
			elif listType == 2:
				self.unsortedList = self.generateInverseList(n)
			if opt == 1:
				self.heapSortValues.append(self.sortSelect(self.unsortedList, self.tests, opt))
			elif opt == 2:
				self.bubbleSortValues.append(self.sortSelect(self.unsortedList, self.tests, opt))
			elif opt == 3:
				self.insertionSortValues.append(self.sortSelect(self.unsortedList, self.tests, opt))
			elif opt == 4:
				self.mergeSortValues.append(self.sortSelect(self.unsortedList, self.tests, opt))
			elif opt == 5:
				self.quickSortValues.append(self.sortSelect(self.unsortedList, self.tests, opt))
			elif opt == 0:
				self.heapSortValues.append(self.sortSelect(self.unsortedList, self.tests, 1))
				self.bubbleSortValues.append(self.sortSelect(self.unsortedList, self.tests, 2))
				self.insertionSortValues.append(self.sortSelect(self.unsortedList, self.tests, 3))
				self.mergeSortValues.append(self.sortSelect(self.unsortedList, self.tests, 4))
				self.quickSortValues.append(self.sortSelect(self.unsortedList, self.tests, 5))

		if opt == 1:
			self.printValues(self.heapSortValues)
			self.generatePlot(self.heapSortValues, "HeapSort")
		elif opt == 2:
			self.printValues(self.bubbleSortValues)
			self.generatePlot(self.bubbleSortValues, "BubbleSort")
		elif opt == 3:
			self.printValues(self.insertionSortValues)
			self.generatePlot(self.insertionSortValues, "InsertionSort")
		elif opt == 4:
			self.printValues(self.mergeSortValues)
			self.generatePlot(self.mergeSortValues, "MergeSort")
		elif opt == 5:
			self.printValues(self.quickSortValues)
			self.generatePlot(self.quickSortValues, "QuickSort")
		elif opt == 0:
			self.generatePlotAll()
	def printValues(self, values):
		'''Método que chama o/s algoritmo/s a testar conforme a opção escolhida para gerar 
		os tempos, imprimi-los na consola e chamar a função para criar o gráfico com esses valores
		@param values -> lista de valores para serem imprimidos
		'''
		self.n = [n for n, media, var in values]
		self.m = [media*(10**-6) for n, media, var in values]
		self.v = [var*(10**-6) for n, media, var in values]
		self.e = [(abs(media - var / media))*(10**-6) for n, media, var in values]
		for i in range(len(values)):
			print (u"Elementos: %s | Média: %s\u03BCs | Variância: %s\u03BCs | Erro Relativo %s\u03BCs"
				%(self.n[i],self.m[i],self.v[i],self.e[i]))
	def sortSelect(self, unsortedList, tests, opt):
		'''Método que selecciona o algoritmo a ser usado conforme a opção escolhida e chama o método 
		para fazer os calculos com os tempos obtidos
		@param tests -> número de testes a realizar em cada cada lista
		@param opt -> opção escolhida
		@param unsortedList -> lista para ser ordenada
		'''
		self.unsortedList = unsortedList
		self.tests = tests
		times = []
		for k in range(tests):
			time1 = clock()
			if opt == 1:
			    HeapSort(unsortedList)
			elif opt == 2:
			    Bubble(unsortedList)
			elif opt == 3:
			    InsertionSort(unsortedList)
			elif opt == 4:
				MergeSort(unsortedList,0, len(unsortedList)-1)
			elif opt == 5:
				QuickSort(unsortedList,0, len(unsortedList)-1)
			time2 = clock()
			times.append(time2-time1)
		return self.calcAverageVar(len(unsortedList), times)

	def generatePlot(self, values, name):
		'''Método que cria e mostra o gráfico individual do algoritmo com as médias
		e a margem de erro relativa tanto superior como inferior para cada lista com 
		um númeero de elementos diferentes
		@param values -> lista de valores gerar o gráfico
		@param name -> nome do algoritmo para aparecer no gráfico
		'''
		plt.grid(True)
		plt.ylabel(u'T(n) - Tempo de execução médio em microsegundos')
		plt.xlabel(u'n - Número de elementos')

		x = [n for n, media, var in values]
		y = [media for n, media, var in values]
		z1 = [media + var / media for n, media, var in values]
		z2 = [media - var / media for n, media, var in values]
		z3 = self.expectedCurve(values)

		plt.plot(x, y,'r', label=name)
		plt.plot(x, z1,'b', linestyle='--', label="Margem de erro +")
		plt.plot(x, z2,'b', linestyle='--', label="Margem de erro -")
		plt.plot(x, z3,'k', linestyle='--', label="Resultado esperado")

		plt.legend()
		plt.show()

	def generatePlotAll(self):
		'''Método que cria e mostra o gráfico com as médias de todos os algoritmos
		para cada lista com um número diferente de elementos
		'''
		plt.grid(True)
		plt.ylabel(u'T(n) - Tempo de execução médio em microsegundos')
		plt.xlabel(u'n - Número de elementos')

		X1 = [n for n, media, var in self.heapSortValues]
		Y1 = [media for n, media, var in self.heapSortValues]

		X2 = [n for n, media, var in self.bubbleSortValues]
		Y2 = [media for n, media, var in self.bubbleSortValues]

		X3 = [n for n, media, var in self.insertionSortValues]
		Y3 = [media for n, media, var in self.insertionSortValues]

		X4 = [n for n, media, var in self.mergeSortValues]
		Y4 = [media for n, media, var in self.mergeSortValues]

		X5 = [n for n, media, var in self.quickSortValues]
		Y5 = [media for n, media, var in self.quickSortValues]

		plt.plot(X1,Y1,'r', label='HeapSort')
		plt.plot(X2,Y2,'b', label='BubbleSort')
		plt.plot(X3,Y3,'y', label='InsertionSort')
		plt.plot(X4,Y4,'k', label='MergeSort')
		plt.plot(X5,Y5,'g', label='QuickSort')

		plt.legend()
		plt.show()

Main()
